#include <stdio.h>
#include <stdlib.h>

typedef struct Single_Cycle_Link_list Link_List_t;
typedef struct Single_Cycle_Link_list* pLink_List_t;

struct Single_Cycle_Link_list
{
    int data;
    struct Single_Cycle_Link_list *next;
};

// 有空节点的链表
// 头节点不存放数据
pLink_List_t Single_Cycle_Link_List_Init()
{
    pLink_List_t phead = (pLink_List_t)malloc(sizeof(Link_List_t));
    if (phead == NULL)
    {
        perror("malloc Single_Link_List fail");
        return phead;
    }
    phead->data = 0;
    phead->next = phead;

    return phead;
}

pLink_List_t Create_new_node(int data)
{
    pLink_List_t pnew = (pLink_List_t)malloc(sizeof(Link_List_t));
    if (pnew == NULL)
    {
        perror("malloc a new node fail");
        return NULL;
    }
    pnew->data = data;
    pnew->next = NULL;
    return pnew;
}

// 头插
#if 1
void Single_Cycle_Link_List_Head_Insert(pLink_List_t phead, pLink_List_t node)
{
    pLink_List_t plink = phead;
    if (node == NULL)
    {
        perror("Head insert a node fail");
        return;
    }
    // 判断是否首节点
    if (phead->next == phead)
    {
        plink->next = node;
        node->next = phead;
        return;
    }
    // 头插
    node->next = phead->next;
    phead->next = node;
}
#endif

#if 1
// 尾插
void Single_Cycle_Link_List_Tail_Insert(pLink_List_t phead, pLink_List_t node)
{
    pLink_List_t plink = phead->next;
    if (node == NULL)
    {
        perror("Tail Insert fail");
        return;
    }
    // 判断有无首节点
    if (phead->next == phead)
    {
        plink = node;
        node->next = phead;
        return;
    }

    // 指针移到最后一个节点
    while (plink->next != phead)
    {
        plink = plink->next;
    }
    plink->next = node;
    node->next = phead;
}
#endif

#if 1
// 头删
void Single_Cycle_Link_List_Head_Delet(pLink_List_t phead)
{
    // 是否有首节点
    if (phead->next == phead)
    {
        return;
    }

    pLink_List_t plink = phead->next;
    pLink_List_t temp = phead->next->next;

    free(plink);
    phead->next = temp;
}
#endif

//任意删，用于查找后删除节点
void Single_Cycle_Link_List_Random_Delet(pLink_List_t phead,int data)
{
    pLink_List_t plink=phead;
    pLink_List_t ptemp=NULL;
    //plink指向需要删除节点的前一个节点
    while(plink->next->data!=data)
    {
        if(plink->next==phead)
        {
            printf("链表中无此数据\n");
            return;
        }

        plink=plink->next;
    }
    ptemp=plink->next;
    plink->next=ptemp->next;
    free(ptemp);
    ptemp=NULL;
}


#if 1
// 尾删
void Single_Cycle_link_List_Tail_Delet(pLink_List_t phead)
{
    // 判断是否有首节点
    if (phead->next == phead)
    {
        printf("链表不存在首节点");
        return;
    }

    // 判断是否只剩首节点了
    if (phead->next->next == phead)
    {
        free(phead->next);
        phead->next = phead;
        return;
    }

    pLink_List_t plink = phead->next;
    pLink_List_t ptemp = NULL;

    while (plink->next->next != phead)
    {
        plink = plink->next;
    }
    ptemp = plink->next;
    plink->next = phead;
     free(ptemp);
}
#endif

#if 1
// 查找数据
void Single_Cycle_Link_List_Search(pLink_List_t phead, int data)
{
    if (phead->next == phead)
    {
        printf("链表首节点");
        return;
    }

    pLink_List_t plink = phead->next;

    while (plink != phead)
    {
        if (plink->data == data)
        {
            printf("已经找到数据%d\n", plink->data);
            return;
        }
        plink = plink->next;
    }

    if (plink == phead)
    {
        printf("链表中找不到此数据\n");
        return;
    }
}
#endif

#if 1
// 修改数据
void Single_Cycle_Link_List_Modify(pLink_List_t phead, int data, int modified_data)
{
    if (phead->next == phead)
    {
        printf("链表首节点");
        return;
    }

    pLink_List_t plink = phead->next;

    while (plink != phead)
    {
        if (plink->data == data)
        {
            plink->data = modified_data;
            return;
        }
        plink = plink->next;
    }

    if (plink == phead)
    {
        printf("链表中找不到此数据\n");
        return;
    }
}
#endif

// 遍历链表
#if 1
void Print_Link_List(pLink_List_t phead)
{
    pLink_List_t plink = phead->next;

    if (plink == phead)
    {
        perror("None Link List");
        return;
    }

    while (plink != phead)
    {
        printf("%d  ", plink->data);
        plink = plink->next;
    }
    printf("\n");
}
#endif

#if 1
// 释放链表
void Release_Cycle_Link_list(pLink_List_t phead)
{
    pLink_List_t plink = phead->next;
    pLink_List_t ptemp = NULL;

    while (plink != phead)
    {
        ptemp = plink->next;
        free(plink);
        plink = ptemp;
    }
    free(phead);
    printf("链表已经全部释放\n");
}
#endif

int main()
{
    pLink_List_t phead = NULL;
    phead = Single_Cycle_Link_List_Init();
    Single_Cycle_Link_List_Head_Insert(phead, Create_new_node(1));
    Single_Cycle_Link_List_Head_Insert(phead, Create_new_node(2));
    Single_Cycle_Link_List_Head_Insert(phead, Create_new_node(3));
    Single_Cycle_Link_List_Tail_Insert(phead, Create_new_node(7));
    Single_Cycle_Link_List_Tail_Insert(phead, Create_new_node(8));
    Single_Cycle_Link_List_Tail_Insert(phead, Create_new_node(9));
    Print_Link_List(phead);
    Single_Cycle_Link_List_Random_Delet(phead, 3);
    Single_Cycle_Link_List_Random_Delet(phead, 1);
    Single_Cycle_Link_List_Random_Delet(phead, 9);
    Print_Link_List(phead);
    Release_Cycle_Link_list(phead);
    return 0;
}